Міністерство Освіти і Науки України Національний Університет “Львівська Політехніка”
Кафедра ЕОМ ПАРАЛЕЛЬНІ АЛГОРИТМИ МНОЖЕННЯ МАТРИЦІ НА ВЕКТОР Методичні вказівкидо лабораторної роботи № 4 з курсу “Паралельні та розподілені обчислення” для студентів базового напряму 6.0915  -  “Комп’ютерна інженерія” Затвердженона засіданні кафедри”Електронні обчислювальні машини”Протокол № _ від 2010 року Львів – 2010  Паралельні алгоритми множення матриці на вектор: Методичні вказівки до лабораторної роботи № 4 з курсу “Паралельні та розподілені обчислення” для студентів базового напряму 6.0915  -  “Комп’ютерна інженерія”/ Укладачі: Є. Ваврук, О. Акимишин – Львів: Національний університет “Львівська політехніка”, 2010, 14  с. Укладачі: Є. Ваврук, к.т.н., доцент. О. Акимишин, к.т.н., асистент Відповідальний за випуск: Мельник А. О., професор, завідувач кафедри Рецензенти: Попович Р.Б., к. т. н, доцент Юрчак І.Ю., к. т. н, доцент МЕТА РОБОТИ Ознайомитись з методами організації паралельного множення матриці на вектор та розробити паралельну програму з використанням технології MPI. ТЕОРЕТИЧНІ ВІДОМОСТІ: Матриці та операції над ними широко використовуються при математичному моделюванні найрізноманітніших процесів, явищ і систем. Матричні обчислення складають основу багатьох наукових і інженерних розрахунків. Враховуючи важливість ефективного виконання матричних обчислень багато стандартних бібліотек програм містять процедури для різних матричних операцій. Об'єм програмного забезпечення для операцій над матрицями постійно збільшується - розробляються нові оптимальні структури даних для зберігання матриць спеціального типу (трикутних, стрічкових, розріджених тощо), створюються різні високоефективні машинно-залежні реалізації алгоритмів, проводяться теоретичні дослідження для пошуку швидших методів матричних обчислень. Будучи обчислювально трудомісткими, матричні обчислення є класичною областю застосування паралельних обчислень. З одного боку, використання високопродуктивних багатопроцесорних систем дозволяє істотно підвищити складність завдань, які розв’язуються. З іншого боку, через своє достатньо просте формулювання матричні операції надають прекрасну можливість для демонстрації багатьох прийомів і методів паралельного програмування. У даній лабораторній роботі аналізуються методи паралельних обчислень для операції векторно-матричного множення. 1. Принципи розпаралелювання Для багатьох методів матричних обчислень характерним є повторення одних і тих же операцій для різних даних. Дана властивість свідчить про наявність паралелізму за даними при виконанні матричних обчислень, і, як результат, розпаралелювання матричних операцій зводиться, в більшості випадків, до розбиття оброблюваних матриць між процесорами використовуваної обчислювальної системи. Вибір способу поділу матриць приводить до визначення конкретного методу паралельних обчислень; існування різних схем розподілу даних породжує ряд паралельних алгоритмів матричних обчислень. Найбільш загальні і широко використовувані способи поділу матриць полягають в розбитті даних на смуги (по вертикалі або горизонталі) або на прямокутні фрагменти (блоки). 1.1. Стрічкове розбиття матриці. При стрічковому (block-striped) розбитті кожному процесору виділяється певна підмножина рядків (rowwise або горизонтальне розбиття) або стовпців (columnwise або вертикальне розбиття) матриці. При такому підході для горизонтального розбиття по рядках, наприклад, матриця A представляється у вигляді (1)
, де (1) ai = (ai1,ai2,...,ain), 0 <= i < m i-й рядок матриці A (передбачається, що кількість рядків m кратна кількості процесорів p, тобто m = k·p). Інший можливий підхід до формування смуг полягає в застосуванні тієї чи іншої схеми чергування (циклічності) рядків або стовпців. Як правило, для чергування використовується кількість процесорів p - в цьому випадку при горизонтальному розбитті матриця A приймає вигляд
(2) 1.2. Блокове розбиття матриці. При блоков...